#include <stdio.h>

void hanoi(int N, int d);
void shift(int N, int d);

int count_trailing_zeros(int N);

int main(){
    // 测试3个盘子
    printf("Testing 3 pegs start...\n");
    hanoi(3,1);
    printf("Testing 3 pegs end....\n");

    //测试5个盘子
    printf("Testing 5 pegs start...\n");
    hanoi(5,1);
    printf("Testing 5 pegs end...\n");

    return 0;
}

int count_trailing_zeros(int N){
    int count = 0;
    if (N == 0) {
        return count;
    }
    while ((N&0x1)==0) {
        N >>= 1;
        count++;
    }
    return count;
}

void hanoi(int N, int d){
    if (N == 0) {
        return ;
    }
    //先把N-1个盘子向左移动
    hanoi(N-1, -d);
    //再把第N个盘子向右移动
    shift(N, d);
    //最后把N-1个盘子向左移动到第N个盘子上
    hanoi(N-1, -d);
}

void shift(int N, int d){
    if (d > 0) {
        printf("shift(%d, +%d)\n", N,d);
    }else {
        printf("shift(%d, %d)\n", N,d);
    }
    
}